//题目：
//题目:
// 你有一个背包，最多能容纳的体积是V。

// 现在有n种物品，每种物品有任意多个，第i种物品的体积为vi,​价值为wi。
// （1）求这个背包至多能装多大价值的物品？
// （2）若背包恰好装满，求至多能装多大价值的物品？

// 数据范围： 1≤v,vi,wi≤1000;
#include<iostream>
#include<cstring>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    //01背包
    // vector<int> knapsack(int v, int n, vector<vector<int> >& nums) 
    // {
        
    //     // // write code here  nums[i][0]：体积   nums[i][1]：价值
    //     // vector<int> ret;
    //     // //1.创建dp表————dp[i][j]表示：背包装载第i个物品、体积不超过j时的最大价值
    //     // vector<vector<int>> dp(n+1,vector<int>(v+1));
    //     // //2.初始化————暂无
    //     // //3.填表————动态转移方程
    //     // for(int i=1;i<=n;i++)
    //     // {
    //     //     for(int j=1;j<=v;j++)
    //     //     {
    //     //         dp[i][j]=dp[i-1][j];//不装第i个物品
    //     //         if(j-nums[i-1][0]>=0)
    //     //             dp[i][j]=max(dp[i][j],dp[i-1][j-nums[i-1][0]]+nums[i-1][1]);//装第i个物品
    //     //     }
    //     // }
    //     // //4.确定第一个返回值
    //     // ret.push_back(dp[n][v]);

    //     // //创建第二个dp表————dp[i][j]表示：背包装载第i个物品、体积等于j时的最大价值
    //     // memset(&dp,0,sizeof(dp));
    //     // //2.初始化
    //     // for(int j=1;j<=v;j++)
    //     //     dp[0][j]=-1;//表示这种状态不存在
    //     // //3.填表————动态转移方程
    //     // for(int i=1;i<=n;i++)
    //     // {
    //     //     for(int j=1;j<=v;j++)
    //     //     {
    //     //         dp[i][j]=dp[i-1][j];//不装第i个物品
    //     //         if(j-nums[i-1][0]>=0 && dp[i-1][j-nums[i-1][0]]!=-1)
    //     //             dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i-1][0]]+nums[i-1][1]);//装第i个物品
    //     //     }
    //     // }
    //     // //4.确定第一个返回值
    //     // if(dp[n][v]==-1)dp[n][v]=0;
    //     // ret.push_back(dp[n][v]);
    //     // return ret;

    //     //空间优化O(N^2)————>O(N)
    //     vector<int> ret;
    //     //1.创建dp表————dp[i][j]表示：背包装载第i个物品、体积不超过j时的最大价值
    //     vector<int> dp(v+1);
    //     //2.初始化————暂无
    //     //3.填表————动态转移方程
    //     for(int i=1;i<=n;i++)
    //     {
    //         for(int j=v;j>=nums[i-1][0];j--)
    //             dp[j]=max(dp[j],dp[j-nums[i-1][0]]+nums[i-1][1]);//装第i个物品
    //     }
    //     //4.确定第一个返回值
    //     ret.push_back(dp[v]);

    //     //创建第二个dp表————dp[i][j]表示：背包装载第i个物品、体积等于j时的最大价值
    //     memset(&dp,0,sizeof(dp));
    //     //2.初始化
    //     for(int j=1;j<=v;j++)
    //         dp[j]=-1;//表示这种状态不存在
    //     //3.填表————动态转移方程
    //     for(int i=1;i<=n;i++)
    //     {
    //         for(int j=v;j>=nums[i-1][0];j--)
    //         {
    //             if(dp[j-nums[i-1][0]]!=-1)
    //                 dp[j]=max(dp[j],dp[j-nums[i-1][0]]+nums[i-1][1]);//装第i个物品
    //         }
    //     }
    //     //4.确定第一个返回值
    //     if(dp[v]==-1)dp[v]=0;
    //     ret.push_back(dp[v]);

    //     return ret;
    // }

    //完全背包
    vector<int> knapsack(int v, int n, vector<vector<int> >& nums) 
    {
        
        // write code here  nums[i][0]：体积   nums[i][1]：价值
        // vector<int> ret;
        // //1.创建dp表————dp[i][j]表示：背包装载第i个物品、体积不超过j时的最大价值
        // vector<vector<int>> dp(n+1,vector<int>(v+1));
        // //2.初始化————暂无
        // //3.填表————动态转移方程
        // for(int i=1;i<=n;i++)
        // {
        //     for(int j=1;j<=v;j++)
        //     {
        //         //法一:暴力遍历对nums[i-1]物品的拾取次数
        //         // for(int k=0;k*nums[i-1][0]<=j;k++)
        //         //     dp[i][j]=max(dp[i][j],dp[i-1][j-k*nums[i-1][0]]+k*nums[i-1][1]);//装第i个物品

        //         //法二：数学法优化
        //         dp[i][j]=dp[i-1][j];
        //         if(j-nums[i-1][0]>=0)
        //             dp[i][j]=max(dp[i-1][j],dp[i][j-nums[i-1][0]]+nums[i-1][1]);
        //     }
        // }
        // //4.确定第一个返回值
        // ret.push_back(dp[n][v]);

        // //创建第二个dp表————dp[i][j]表示：背包装载第i个物品、体积等于j时的最大价值
        // memset(&dp,0,sizeof(dp));
        // dp.resize(n+1,vector<int>(v+1));
        // //2.初始化
        // for(int j=1;j<=v;j++)
        //     dp[0][j]=-1;//表示这种状态不存在
        // //3.填表————动态转移方程
        // for(int i=1;i<=n;i++)
        // {
        //     for(int j=1;j<=v;j++)
        //     {
        //         dp[i][j]=dp[i-1][j];
        //         //法一：暴力遍历对nums[i-1]物品的拾取次数
        //         // for(int k=0;k*nums[i-1][0]<=j;k++)
        //         //     if(dp[i-1][j-k*nums[i-1][0]]!=-1)
        //         //         dp[i][j]=max(dp[i][j],dp[i-1][j-k*nums[i-1][0]]+k*nums[i-1][1]);//装第i个物品

        //         //法二：数学优化
        //         if(j-nums[i-1][0]>=0 && dp[i][j-nums[i-1][0]]!=-1)
        //             dp[i][j]=max(dp[i-1][j],dp[i][j-nums[i-1][0]]+nums[i-1][1]);
        //     }
        // }
        // //4.确定第一个返回值
        // if(dp[n][v]==-1)dp[n][v]=0;
        // ret.push_back(dp[n][v]);
        // return ret;

        //空间优化O(N^2)————>O(N)
        vector<int> ret;
        //1.创建dp表————dp[i][j]表示：背包装载第i个物品、体积不超过j时的最大价值
        vector<int> dp(v+1);
        //2.初始化————暂无
        //3.填表————动态转移方程
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=v;j++)
            {
                //法一:暴力遍历对nums[i-1]物品的拾取次数
                // for(int k=0;k*nums[i-1][0]<=j;k++)
                //     dp[i][j]=max(dp[i][j],dp[i-1][j-k*nums[i-1][0]]+k*nums[i-1][1]);//装第i个物品

                //法二：数学法优化
                if(j-nums[i-1][0]>=0)
                    dp[j]=max(dp[j],dp[j-nums[i-1][0]]+nums[i-1][1]);
            }
        }
        //4.确定第一个返回值
        ret.push_back(dp[v]);

        //创建第二个dp表————dp[i][j]表示：背包装载第i个物品、体积等于j时的最大价值
        memset(&dp,0,sizeof(dp));
        dp.resize(v+1);
        //2.初始化
        for(int j=1;j<=v;j++)
            dp[j]=-1;//表示这种状态不存在
        //3.填表————动态转移方程
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=v;j++)
            {
                //法一：暴力遍历对nums[i-1]物品的拾取次数
                //dp[i][j]=dp[i-1][j]
                // for(int k=0;k*nums[i-1][0]<=j;k++)
                //     if(dp[i-1][j-k*nums[i-1][0]]!=-1)
                //         dp[i][j]=max(dp[i][j],dp[i-1][j-k*nums[i-1][0]]+k*nums[i-1][1]);//装第i个物品

                //法二：数学优化
                if(j-nums[i-1][0]>=0 && dp[j-nums[i-1][0]]!=-1)
                    dp[j]=max(dp[j],dp[j-nums[i-1][0]]+nums[i-1][1]);
            }
        }
        //4.确定第一个返回值
        if(dp[v]==-1)dp[v]=0;
        ret.push_back(dp[v]);
        return ret;
    }
};